The present invention relates to data storage and retrieval systems. More particularly, the present invention relates to a method and apparatus for coded symbol stuffing in optical and magnetic recording systems where run length limiting coding schemes are used.
Generally, both data storage/retrieval systems and data transmission systems communicate information. Storage/retrieval systems communicate information through time, while data transmission systems communicate information through space. Typically, data storage and retrieval systems use a read/write head to communicate data to a corresponding one of substantially concentric tracks or channels in the media Using various modulation techniques, data transmission systems similarly communicate data over channels in the transmission media or receive data from channels in the media. Storage/retrieval systems and data transmission systems often utilize encoding/decoding schemes for error detection, for privacy, and for data compression.
One common type of coding scheme is referred to as Run Length Limiting. Run length limiting encoding schemes involve separating consecutive “1s” in a binary sequence by some predefined number of zeros. Coded data sequences having this property are referred to as Ran Length Limited (RLL) codes.
Conventional systems that utilize RLL coding schemes, such as optical and magnetic storage systems, as well as in some communication systems, typically include an outer error correcting code (ECC), and a run length limiting (RLL) encoder. Such systems may also include an optional inner channel encoder. Data is encoded first by the ECC, then passed through the RLL encoder. If the optional inner channel encoder is used, the RLL encoded data is then passed through the inner channel encoder. The output of either the RLL encoded data or the inner channel encoded data can then be precoded before being recorded onto channels on the media.
Typically, at the detection side, a Viterbi detector is used to reconstruct the coded bits from the channel; however, due to electronic and media noise in the channel, conventional detectors cannot recover the original data with an arbitrarily small error probability. To correct errors after the coded bits are reconstructed by the Viterbi detector, an ECC decoder is used at the output of the read/write channel. Generally, the ECC decoder decreases the output Bit-Error Rate (BER) and the Sector Failure Rate (SFR) of the channel to the levels typically provided in the technical specifications for the implementing apparatus.
It is known that the RLL code typically facilitates the operation of the timing circuits. At the same time, the RLL code shapes the spectrum of the signal and modifies the distance properties of the output code words of the channel. Since the RLL code effects both the shape of the signal spectrum and the distance properties of the output, the RLL code can be used to improve the BER and the SFR characteristics of the system.
Conventional RLL coding schemes employ a state transition diagram. In a finite state encoder, arbitrary user data (p) is encoded to constraint data (q) via a finite state machine, where p and q represent sequences of data objects, each containing two or more elements. The data rate of the encoder can be defined as p/q (“p divided by q”), provided that, at each stage of the encoding process, one P-object of user data (p) is encoded to one q-object of constraint data (q) in such a way that the concatenation of the encoded q-objects obeys the given constraint.
The finite-state machine has multiple states, and the encoder or decoder moves from one state to another after the generation of each output object. A single error in the received sequence can trigger the generation of wrong states in the decoder, resulting in long sequences of errors. This phenomenon is referred to as error propagation.
It is expected that the received sequence to be decoded will not be identical to the transmitted sequence due to a variety of factors, such as inter-symbol interference (ISI), damage to the storage medium, noise, and the like. These factors lead to errors in the decoded sequence, and the decoder must account for these errors. For the purpose of limiting error propagation, the decoder can be implemented via a sliding-block decoder, which is a decoder having a decoding window of a fixed size. The encoded data sequence is decoded a portion at a time, such that recovery of a specific original bit involves only a portion of the received sequence. Specifically, the portion of the received sequence being decoded is the portion of the sequence that falls within the decoding window of the specific bit. Thus, the decoding process can be considered as a sequence of decoding decisions where the decoding window “slides” over the sequence to be decoded. The sliding block decoder limits errors in the received sequence such that the error only influences the decoding decisions made within the window, thereby effecting only a limited number of recovered bits.
The size of the decoding window of a sliding block decoder is relatively significant. The size of the window provides an upper bound to the expected amount of error propogation and it provides an indication of the complexity of the decoder (and the corresponding size of the decoder's hardware implementation).
One technique for constructing finite state encoders is the state-splitting algorithm, which reduces design procedure a series of steps. As a design technique, the state-splitting algorithm works well for small and moderate values of p, but when p is relatively large, the state-splitting algorithm encounters simply too many possible assignments of data-to-codeword in the encoding graph, making design difficult. Moreover, a poor choice of assignments, given the complexity, could lead to a costly implementation. In practice, the implemented design should include the fewest possible number of states. However, the state-splitting algorithm does not directly solve the general problem of designing codes that achieve, for example, the minimum number of encoder states, the smallest sliding-block decoding window, or the minimum hardware complexity (a less precise valuation).
Recently, various types of iterative detection and decoding schemes were developed for use in data storage and data communication systems, based on turbo codes, Low Density Parity Check (LDPC) codes, and turbo product codes. These types of codes provide very low BERs, but they usually require the use of an interleaver after the RLL and optional inner channel encoder(s). An interleaver changes the order of the bits in a sequence. By processing the already encoded bits with an interleaver, the interleaver changes the order of the already encoded bits, which can effectively nullify the operation of the RLL encoder. Since encoders based on finite-state machines transform all (or almost all) data bits while generating the output code words, the use of such codes in channels with interleaving coded bits is virtually impossible, or at least severely restricted.